package com.mlh.dp.old;
//
// 题目：
// 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
// 举例：
// 输入：s = "rabbbit", t = "rabbit"
// 输出：3
// 解释：
// 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
// rabbbit
// ---- --
// rabbbit
// -- ----
// rabbbit
// --- ---
public class DifferentSubsequences {

//leetcode题解
//     假设字符串s和t的长度分别为m和n。如果t是s的子序列，则s的长度定大于或等于t
//     的长度，即只有当m≥n时，t才可能是s的子序列。如果m<n, 则t-定不是s的子序列，
//     因此直接返回0。
//     当m≥n时，可以通过动态规划的方法计算在s的子序列中t出现的个数。
//     创建二维数组dp,其中dp[i][j]表示在s[i:]的子序列中t[j:]出现的个数。
//     考虑动态规划的边界情况:
//     当j=n时，t[j:]为空字符串，由于空字符串是任何字符串的子序列，因此对任意0≤i≤m,有dp[i][n]=1;
//     当i=m且j<n时，s[i:]为空字符串，t[j:]为非空字符串，由于非空字符串不是空字符串的子序列，因此对任意0≤j<n, 有dp[m][j]=0.
//     当i<m且j<n时，考虑dp[i][j]的计算:
//             ●当s[i]=t[j]时，dp[i][j]由两部分组成:
//             如果s[i]和t[j]匹配，则考虑t[j+1:]作为s[i+1:]的子序列，子序列数为dp[i+1][i+1];
//             如果s[i]不和t[j]匹配，则考虑t[j:]作为s[i+1:]的子序列，子序列数为dp[i+1][j]。
//                     (这里可能有录友不明白了，为什么还要考虑 不用s[i-1]来匹配，都相同了指定要匹配啊。
//                     例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。
//                     当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。
//                     (dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。))
//     因此当s[i]=t[j] 时，有dp[i][j]=dp[i+1][j+1]+dp[i+1][i].
//             ●当s[i]≠t[j]时，s[i]不能和t[i]匹配，因此只考虑t[j:]作为s[i+1:]的子序列，子序列数为dp[i+1][j]。
//     因此当s[i]≠t[j]时，有dp[i][j]=dp[i+1][j]。
//     由此可以得到如下状态转移方程:
//     最终计算得到dp[0][0]即为在s的子序列中t出现的个数。

    //根据题解自己写出的代码，题解是从尾到头， 我自己写得是从头到尾  其思想都是相同的
    //像这种2个字符串的dp问题，一般都是构造二维dp数组  我们需要做的是思考这个dp数组表示什么
    //并且去思考出状态转移方程
    //之前做的 编辑距离  还有两个字符串的最小ASCII删除和  也是双字符串题目
    public static int method1(String s,String t){
        char[]ss=s.toCharArray();
        char[]tt=t.toCharArray();
        int[][]dp =new int[tt.length+1][ss.length+1];

        for(int i=1;i<=tt.length;i++){
            dp[i][0]=0;
        }
        for(int i=0;i<=ss.length;i++){
            dp[0][i]=1;
        }

        for(int i=1;i<=tt.length;i++){
            for(int j=1;j<=ss.length;j++){
                //当 i>j 不可能会有符合的子序列出现
                if(i>j){
                    continue;
                }
                if(tt[i-1]==ss[j-1]){
                    dp[i][j]=dp[i-1][j-1]+dp[i][j-1];
                }else{
                    dp[i][j]=dp[i][j-1];
                }
            }
        }
        return dp[t.length()][s.length()];
    }
}
